﻿#light
// Queue amortized by bankers method

namespace FunctionalStructures

// Очередь состоит из двух списков
// 1. Front - список из которого извлекаются элементы
// 2. Rear - список в который помещаются элементы
// Если после добавления нового элемента, задний список становится длиннее переднего, он разворачивается 
// и помещается в конец переднего списка. 
// Сложность извлечения O(1)

type 'a AmortizedQueue = 
    | Queue of int * 'a LazyList * int * 'a LazyList // front * rear

    member this.Count = match this with Queue(fLen, front, rLen, rear) -> fLen + rLen

    static member Empty = Queue(0, LazyList.Empty<'a>, 0, LazyList.Empty<'a>)
    
    static member private check (queue: AmortizedQueue<'a>) = 
        match queue with 
            |Queue(frontLength, frontList, rearLength, rearList) ->
                if rearLength <= frontLength then queue
                else Queue(rearLength + frontLength, LazyList.Concat frontList (LazyList.Reverse rearList), 0, LazyList.Empty<'a>)
    
    
    // Put value to the rear list
    // If list.length > front list.length then reverse rear and merge with front.
    member this.Snoc (value : 'a) = 
        match this with 
            Queue(frontLength, frontList, rearLength, rearList) ->  
                Queue(frontLength, frontList, rearLength + 1, LazyList.Add value rearList) 
                |> AmortizedQueue<'a>.check

    // Get Value from the front list
    member this.Head = 
        match this with
            |Queue(0, _, rearLength, rear) -> failwith "Empty"
            |Queue(fl, front, rearLength, rear) -> LazyList.Head front

    member this.Tail = 
        match this with
            |Queue(0, _, rearLength, rear)-> failwith "Empty"
            |Queue(fl, front, rearLength, rear) -> Queue(fl-1, LazyList.Tail front, rearLength, rear) |> AmortizedQueue<'a>.check
